
#pragma once

#include <string>

//Represents big unsigned integer number.
template <size_t bit_size>
class BigUnsignedInt
{
	private:
		unsigned int data[bit_size / 32 + (bit_size % 32 == 0 ? 0 : 1)];
		size_t size;
	public:
		//Creates big integer with initial value.
		inline BigUnsignedInt(unsigned int value = 0)
		{
			size = bit_size / 32 + (bit_size % 32 == 0 ? 0 : 1);
			data[0] = value;
			for (size_t i = 1; i < size; i++)
				data[i] = 0;
		}
		//Sums two big integers.
		inline BigUnsignedInt<bit_size> operator +(const BigUnsignedInt<bit_size> &value) const
		{
			BigUnsignedInt<bit_size> result;
			unsigned __int64 cur = 0;
			for (size_t i = 0; i < size; i++)
			{
				cur += (unsigned __int64)this->data[i] + value.data[i];
				result.data[i] = (unsigned int)cur;
				cur >>= 32;
			}
			return result;
		}
		//Multiplies two big integers.
		inline BigUnsignedInt<bit_size> operator *(const BigUnsignedInt<bit_size> &value) const
		{
			BigUnsignedInt<bit_size> result;
			for (size_t i = 0; i < size; i++)
			{
				unsigned __int64 cur = 0;
				for (size_t j = 0; j < size; j++)
					if (i + j < size)
					{
						cur += (unsigned __int64)this->data[j] * value.data[i] + result.data[i + j];
						result.data[i + j] = (unsigned int)cur;
						cur >>= 32;
					}
			}
			return result;
		}
		//Converts big integer to string.
		inline std::string toString()
		{
			char buf[128];
			std::string res;
			//Getting actual size.
			size_t real_size = size;
			while (real_size > 1 && data[real_size - 1] == 0)
				real_size--;
			//Building result string.
			for (size_t i = 0; i < real_size; i++)
			{
				size_t count = 8 - sprintf(buf, "%X", data[i]);
				res = buf + res;
				if (i != real_size - 1)
					while (count-- > 0)
						res = "0" + res;
			}
			res = "0x" + res;
			return res;
		}
};

//Represents arbitary 2x2 matrix.
//Note: template type "T" must support multiplication and summation.

template <class T>
class Matrix2x2
{
	private:
		T data[4];
	public:
		//Creates zero matrix.
		inline Matrix2x2()
		{ data[0] = data[1] = data[2] = data[3] = (T)0; }
		//Creates matrix with required elements.
		inline Matrix2x2(const T &a11, const T &a12,
						 const T &a21, const T &a22)
		{
			data[0] = a11;
			data[1] = a12;
			data[2] = a21;
			data[3] = a22;
		}
		//Returns element, located at intersection of given row and column.
		inline T &operator() (size_t row, size_t column)
		{ return data[column + row * 2]; }
		inline const T &operator() (size_t row, size_t column) const
		{ return data[column + row * 2]; }
		//Multiplies two matrices.
		inline Matrix2x2<T> operator *(const Matrix2x2<T> &matrix) const
		{
			const Matrix2x2<T> &cur = *this;
			Matrix2x2<T> result(cur(0, 0) * matrix(0, 0) + cur(0, 1) * matrix(1, 0),
								cur(0, 0) * matrix(0, 1) + cur(0, 1) * matrix(1, 1),
								cur(1, 0) * matrix(0, 0) + cur(1, 1) * matrix(1, 0),
								cur(1, 0) * matrix(0, 1) + cur(1, 1) * matrix(1, 1));
			return result;
		}
};
